package my.jwds.p44;

/**
 * 44. 通配符匹配
 * https://leetcode.cn/problems/wildcard-matching/
 */
public class IsMatch {

    public static void main(String[] args) {

        Solution obj = new Solution();

        System.out.println(obj.isMatch( "adceb",
                "*a*b"));
        System.out.println(obj.isMatch("aab",
                "c*a*b"));
        System.out.println(obj.isMatch("abcabczzzde",
                "*abc???de*"));
        long start = System.currentTimeMillis();
        System.out.println("运行时间:" + (System.currentTimeMillis() - start));
    }

    static class Solution {




        public boolean isMatch(String s, String p) {
            int m = s.length(),n = p.length();
            boolean[][] dp = new boolean[n+1][m+1];
            dp[0][0] = true;
            for (int i = 1; i <= n; i++) {
                if (p.charAt(i-1) == '*'){
                    dp[i][0] = dp[i-1][0];
                }
            }
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    if (p.charAt(i-1) == '*'){
                        dp[i][j] = dp[i-1][j-1] || dp[i][j-1] || dp[i-1][j];
                    }else{
                        dp[i][j] = (p.charAt(i-1) == '?' || p.charAt(i-1) == s.charAt(j-1));
                        dp[i][j] = dp[i-1][j-1] && dp[i][j];

                    }
                }
            }
            return dp[n][m];
        }


    }
}